Sau khi Nguyễn Trung Trực bị thực dân Pháp xử chém ngày 27 tháng 10 năm 1868 tại chợ Rạch Giá, những người dân yêu kính ông đã bí mật thờ ông trong đền thờ Nam Hải đại tướng quân (cá voi hay cá ông).

Ban đầu, đây chỉ là một ngôi đền nhỏ bằng gỗ, mái lợp lá do dân chài dựng nên bên dòng sông Kiên (phía trước mặt) và rạch Lăng Ông[gc 1](từ cổng đền nhìn vào, ở phía bên trái) và chỉ cách Biển Đông độ chừng trăm mét.

Qua lần sửa chữa vào năm 1881, ngôi đình đã khang trang hơn. Nhưng để có diện mạo như ngày hôm nay, chính là nhờ lần khởi công sửa chữa lớn vào ngày 20 tháng 12 năm 1964, khánh thành ngày 24 tháng 2 năm 1970, do kiến trúc sư Nguyễn Văn Lợi thiết kế, với toàn bộ kinh phí xây dựng do nhân dân đóng góp.

Nhân dịp này, nhân dân địa phương cũng tạc tượng Nguyễn Trung Trực bằng đồng sơn đen, đặt trước khu "chợ nhà lồng" Rạch Giá.